package lc.q250_300;

import lc.TreeNode;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Q257 {

    public List<String> binaryTreePaths(TreeNode root) {
        List<String> paths = new ArrayList<>();
        dfs(root, paths, "");
        return paths;
//        int val = root.val;
        // 改用dfs，深度优先，一直遍历到叶子节点，然后就是结果，需要保存前路径
//        List<String> lefts = binaryTreePaths(root.left);
//        List<String> rights = binaryTreePaths(root.right);
//        lefts.replaceAll(s -> val + "->" + s);
//        rights.replaceAll(s -> val + "->" + s);
//        lefts.addAll(rights);
//        if (lefts.isEmpty()) {
//            ArrayList<String> strings = new ArrayList<>();
//            strings.add(root.val + "");
//            return strings;
//        }
//        return lefts;
    }

    private void dfs(TreeNode root, List<String> path, String curPath) {
        if (root != null) {
            curPath += root.val;
            // 判断是否为叶子节点
            if (root.left == null && root.right == null) {
                path.add(curPath);
            } else {
                curPath += "->";
                dfs(root.left, path, curPath);
                dfs(root.right, path, curPath);
            }
        }
    }


}
